public class MaxCoins {

    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n + 2][n + 2];
        int[] val = new int[n + 2];
        val[0] = 1;
        val[n + 1] = 1;
        for (int i = 0; i < n; i++) {
            val[i + 1] = nums[i];
        }
        for (int l = 1; l <= n; l++) {
            for (int i = 1; i <= n - l + 1; i++) {
                for (int j = i; j <= i + l - 1; j++) {
                    dp[i][i + l - 1] = Math.max(dp[i][j - 1] + dp[j + 1][i + l - 1] + val[i - 1] * val[i + l] * val[j], dp[i][i + l - 1]);
                }
            }
        }
        return dp[1][n];
    }
}
